package mine.code.question.动态规划;

import org.junit.Test;

import java.util.Arrays;

/**
 * 请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。
 * <p>
 * 输入数组为火柴长度数组
 * <p>
 * 示例1:
 * <p>
 * 输入: [1,1,2,2,2]
 * 输出: true
 * <p>
 * 解释: 能拼成一个边长为2的正方形，每边两根火柴。
 *
 * @author caijinnan
 */
public class _Undone火柴拼正方形 {

    @Test
    public void run() {
//        int[] matchsticks = {1, 1, 2, 2, 2};
//        int[] matchsticks = {3, 3, 3, 3, 4, 4};
        int[] matchsticks = {5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3};
        System.out.println(makesquare(matchsticks));
    }


    public boolean makesquare(int[] matchsticks) {
        if (matchsticks.length < 4) {
            return false;
        }
        Arrays.sort(matchsticks);
        int sum = 0;
        for (int matchstick : matchsticks) {
            sum += matchstick;
        }
        if (sum % 4 != 0) {
            return false;
        }
        int length = sum / 4;
        int[] dp = new int[4];


        return true;
    }
}
